题
我似乎没有正确地理解语言的手段是什么。
例如,让我们说有一种名为LM的语言。我想看看lm是否是递归的,要说,让我们发现我发现从l-halting问题减少到lm。
我假设LM是递归,所以我表明,然后L-HALTING问题也是递归,当然是假的,因此LM不是递归。
但我可以说lm是因为我找到了减少lh到lm的方法吗? 如果不是我如何显示LM是重新的?
解决方案
让我们清除一点,因为有许多可能导致误解的等效/类似的定义。
-
您可以显示语言 $ l $ 是通过构造递归函数 $ \ chi_l $ (或图定机器或任何其他等效计算模型),决定它,即 $$ \ chi_l(x)=begin {is} 1&\ quad; x \在l \\ 0&\ quad; \ text {otw}。 \结束{案例} $$ 请注意,必须为所有输入定义 $ \ chi_l $ 。
-
您可以显示一个语言 $ l $ 不是递归,通过查找来自非的“减少” - 持有人的语言。这可能是你减少的意思,它定义如下:
我们说语言 $ a $ 是语言 $ b $ ,写入 $ a \ le_t b $ ,如果我们可以构建递归函数(或图定机器),可以决定 $ a $ < / span>假设 $ b $ 。
如您所见,从 $ b $ to $ a $ 。
对于任何 $ a $ 和 $ b $ 这样 $ a \ leq_t b $ ,如果 $ b $ 是递归,那么 $ a $ 。
-
您可以显示语言 $ l $ 是 Re,by ConstructionG递归函数 $ \ varphi_l $ (或图定机器) $ dom(\ varphi_l)= l $ (或停止/接受它),例如 $$ \ varphi_l(x)=begin {is} 1&\ quad; x \在l \\ \ Uprarrow&\四边形; \ text {otw。} \结束{案例} $$
其中 $ \ Uprarrow $ 表示“未定义”(或“不停止”)。 Re-ness还有其他定义,就像它的名称“枚举”,你可以轻松观察到相当于这个。
-
但是在显示语言 $ l $ not Re,减少没有帮助,因为它不一定转移重新。例如,观察到 $ \ overline {l_ {halt}} \ leq_t l_ {halt} $ (确实是任何语言都是图灵的补充,反之亦然),但我们知道<跨越类=“math-container”> $ l_ {halt} $ 是re,而 $ \ overline {l_ {halt}} $ 不是。
但还有其他类型的更强的减少转移重新启动。一个这样的减少称为“多次可释放性”:
我们说语言 $ a $ 对语言 $ b $ ,写入 $ a \ leq_m b $ ,如果有总递归函数 $ f $ 这样对于任何输入 $ x $ $$ x \在a \ iff f(x)\中,b $$
这是一个更强的减少了 $ a \ leq_m b $ 表示 $ a \ leq_t b $ (不一定反之亦然)。所以,就像减少一样,它会转移递归。我们也有
对于任何 $ a $ 和 $ b $ 这样 $ a \ leq_m b $ ,如果 $ b $ 是重新的,那么它是 $ a $ 。